Evaluate Expression (hard) #

Given an expression containing digits and operations (+, -, *), find all possible ways in which the expression can be evaluated by grouping the numbers and operators using parentheses.

Example 1:

Input: "1+2*3"
Output: 7, 9
Explanation: 1+(2*3) => 7 and (1+2)*3 => 9

Example 2:

Input: "2*3-4-5"
Output: 8, -12, 7, -7, -3 
Explanation: 2*(3-(4-5)) => 8, 2*(3-4-5) => -12, 2*3-(4-5) => 7, 2*(3-4)-5 => -7, (2*3)-4-5 => -3

Solution #

This problem follows the Subsets pattern and can be mapped to Balanced Parentheses. We can follow a similar BFS approach.

Let’s take Example-1 mentioned above to generate different ways to evaluate the expression.

We can iterate through the expression character-by-character.
we can break the expression into two halves whenever we get an operator (+, -, *).
The two parts can be calculated by recursively calling the function.
Once we have the evaluation results from the left and right halves, we can combine them to produce all results.

Code #

Here is what our algorithm will look like:

  // base case: if the input string is a number, parse and add it to output.
  if (!(input.includes('+')) && !(input.includes('-')) && !(input.includes('*'))) {
    result.push(parseInt(input));
  } else {
    for (let i = 0; i < input.length; i++) {
      const char = input[i];
      if (isNaN(parseInt(char, 10))) { // if not a digit
        // break the equation here into two parts and make recursively calls
        const leftParts = diff_ways_to_evaluate_expression(input.substring(0, i));
        const rightParts = diff_ways_to_evaluate_expression(input.substring(i + 1));
        for (let l = 0; l < leftParts.length; l++) {
          for (let r = 0; r < rightParts.length; r++) {
            let part1 = leftParts[l],
              part2 = rightParts[r];
            if (char === '+') {
              result.push(part1 + part2);
            } else if (char === '-') {
              result.push(part1 - part2);
            } else if (char === '*') {
              result.push(part1 * part2);
            }
          }
        }
      }
    }
  }
 
  return result;
}
 
console.log(`Expression evaluations: ${diff_ways_to_evaluate_expression('1+2*3')}`);
console.log(`Expression evaluations: ${diff_ways_to_evaluate_expression('2*3-4-5')}`);
function diff_ways_to_evaluate_expression(input) {
  const result = [];

Output

2.389s

Expression evaluations: 7,9 Expression evaluations: 8,-12,7,-7,-3

Time complexity #

The time complexity of this algorithm will be exponential and will be similar to Balanced Parentheses. Estimated time complexity will be $O(N*2^N)$ but the actual time complexity ( $O(4^n/\sqrt{n})$ ) is bounded by the Catalan number and is beyond the scope of a coding interview. See more details here.

Space complexity #

The space complexity of this algorithm will also be exponential, estimated at $O(2^N)$ though the actual will be ( $O(4^n/\sqrt{n}).$

Memoized version #

The problem has overlapping subproblems, as our recursive calls can be evaluating the same sub-expression multiple times. To resolve this, we can use memoization and store the intermediate results in a HashMap. In each function call, we can check our map to see if we have already evaluated this sub-expression before. Here is the memoized version of our algorithm; please see highlighted changes: